#if !defined(RASTER_CONVEX_H)
#define RASTER_CONVEX_H

#include <raster/algorithm.h>
#include <typelib/types.h>
#include <cassert>

namespace raster {

int find_edge(int & i, int dir, int n, const point<int> p[]) {
	for (;;) {
		int j = i + dir;
		if (j < 0)
			j = n - 1;
		else
			if (j >= n)
				j = 0;
		if (p[j].y < p[i].y) {	// edge [i, j] goes upwards
			assert(0);
			return -1;			// error
		} else
			if (p[j].y == p[i].y)	// horizontal edge
				i = j;
			else
				return j;		// edge [i, j] goes downwards
	}
}

template <class OP>
void convex(const point<int> p[], int n, OP & op) {

	int ymin	= p[0].y;
	int ymax	= p[0].y;

	int top = 0;
				
	int i;

	// find y-range and topmost point index
	for (i = 1; i < n; ++i)
		if (p[i].y < p[top].y)
			top = i;
		else
			if (p[i].y > ymax)
				ymax = p[i].y;
	ymin = p[top].y;

	if (ymin == ymax) { // degenerate polygon

		int xmin = p[0].x;
		int xmax = p[0].x;

		// find x-range
		for (i = 1; i < n; ++i)
			if (p[i].x < xmin)
				xmin = p[i].x;
			else
				if (p[i].x > xmax)
					xmax = p[i].x;
		// fill it
		horz_line(xmin, xmax, ymin, op);

		return;
	}

	int i1, j1;
	int i2, j2;

	i1 = top;
	j1 = find_edge(i1, -1, n, p);

	i2 = top;
	j2 = find_edge(i2, 1, n, p);

	float x1 = float(p[i1].x);
	float x2 = float(p[i2].x);
	float dx1 = float(p[j1].x - p[i1].x) / (p[j1].y - p[i1].y);
	float dx2 = float(p[j2].x - p[i2].x) / (p[j2].y - p[i2].y);

	for (int y = ymin; y <= ymax; ++y) {

		horz_line(int(x1), int(x2), y, op);

		x1 += dx1;
		x2 += dx2;

		if (y + 1 == p[j1].y) {
			// switch to next node
			i1 = j1;
			if (--j1 < 0)
				j1 = n - 1;
			// check for lower horizontal segment
			if (p[i1].y == p[j1].y)
				break;

			dx1 = float(p[j1].x - p[i1].x) / (p[j1].y - p[i1].y);
		}

		if (y + 1 == p[j2].y) {
			// switch to next node
			i2 = j2;
			if (++j2 < 0)
				j2 = n - 1;
			// check for lower horizontal segment
			if (p[i2].y == p[j2].y)
				break;

			dx2 = float(p[j2].x - p[i2].x) / (p[j2].y - p[i2].y);
		}
	}
}

} // raster

#endif // RASTER_CONVEX_H